package com.qimingyu.linkedlist.linkedreverse;
/**
 * 206. 反转链表
 * 简单
 * 3.3K
 * 相关企业
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 示例 1：
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 * 提示：
 * 链表中节点的数目范围是 [0, 5000]
 * -5000 <= Node.val <= 5000
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */

/*反转链表的第一种方式，创建一个新的链表*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * author cdxyz
 * 解法一
 */
public class ReverseLinkedList1 {
    public static ListNode reverseList(ListNode head) {
        // 创建一个新的链表准备接收原链表中的数据
        /*注意，在赋值之前这个newListHead并不会在内存中创建，
        所以第一次的的while循环中直接当null来用就行*/
        ListNode newListHead = null;

        // 创建一个指针指向原链表的头部
        ListNode p1 = head;

        // 遍历原链表
        /**
         * 思路：循环遍历原链表
         * 先暂存p1的next结点
         * 然后把p1指向新链表的头结点（第一次的时候newListHead为空会直接指向空值）
         * 然后把p1赋值给新链表的头结点
         *
         */
        while (p1 != null) {
            // 暂存下一个节点的指针
            ListNode nextNode = p1.next;
            // 插入到新链表的头部
            p1.next = newListHead;
            newListHead = p1;
            // 移动指针
            p1 = nextNode;
        }
        return newListHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5,null)))));
        ListNode p1 = head;
        while (p1 != null){
            System.out.println("p1中存的值  " + p1.val);
            p1 = p1.next;
        }
        ListNode newHead = reverseList(head);


        System.out.println("----------------");
        ListNode p2 = newHead;
        while (p2 != null){
            System.out.println("p2中存的值  " + p2.val);
            p2 = p2.next;
        }
    }
}

